class Solution {
public:
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    int m;
    int n;
    
    int cutOffTree(vector<vector<int>>& f) {
        m=f.size();
        n=f[0].size();
        vector<pair<int,int>> v;
        for(int i=0;i<m;++i)
        {
            for(int j=0;j<n;++j)
            {
                if(f[i][j]>1)
                {
                    v.push_back({i,j});
                }
            }
        }
        sort(v.begin(),v.end(),
        [&](const pair<int,int>& p1,const pair<int,int>& p2)
        {
            return f[p1.first][p1.second]<f[p2.first][p2.second];
        });

        int x=0;
        int y=0;
        int ret=0;
        for(auto [a,b]:v)
        {
            int step=bfs(f,x,y,a,b);
            if(step==-1) return -1;
            ret+=step;
            x=a;
            y=b;
        }
        return ret;
    }

    int bfs(vector<vector<int>>& f,
    int x1,int y1,int x2,int y2)
    {
        bool arr[51][51]{false};
        int bstep=0;
        queue<pair<int,int>> q;
        q.push({x1,y1});
        arr[x1][y1]=true;
        if(x1==x2&&y1==y2) return bstep;
        while(q.size())
        {
            bstep++;
            int sz=q.size();
            while(sz--)
            {
                auto [a1,b1]=q.front();
                q.pop();
                for(int i=0;i<4;++i)
                {
                    int c=a1+dx[i];
                    int d=b1+dy[i];
                    if(c==x2&&d==y2)
                        return bstep;

                    if(c>=0&&c<m&&d>=0&&d<n&&
                    f[c][d]!=0&&arr[c][d]==false)
                    {
                        arr[c][d]=true;
                        q.push({c,d});
                    }
                }
            }
        }
        return -1;
    }
};
